Bài toán luồng cực đại trên mạng:

Lát cắt. Đường tăng luồng

Định nghĩa. Ta gọi lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng ra thành hai tập X và X*=V \ X, trong đó s ∈ X và t ∈ X*. Khả năng thông qua của lát cắt (X,X*) là số

Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất.

Bổ đề 1. giá trị của mọi luồng f trong mạng luôn nhỏ hơn bằng khả năng thông qua lát cắt (X,X*) bất kỳ trong nó: val(f) £ c(X,X*).

Hệ quả 1. Giá trị luồng cực đại trong mạng không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng.Giả sử f là một luồng trong mạng G = (V,E). Từ mạng G = (V,E) ta xây dựng đồ thị có trọng số trên cung Gf =(V,Ef), với tập cung Ef và trọng số trên các cung được xác định theo quy tắc sau:

 *  Nếu e = (v,w) ∈ E với f(v,w) = 0, thì (v,w)∈ Ef với trọng số c(v,w); *  Nếu e = (v,w) ∈ E với f(v,w) = c(v,w), thì (w,v)∈ Ef với trọng số f(v,w); *  Nếu e = (v,w) ∈ E với 0 <f(v,w) < c(v,w), thì (v,w)∈ Ef với trọng số c(v,w) - f(v,w) và (w,v) ∈ Ef với trọng số f(v,w).

Các cung của Gf đồng thời cũng là cung của G được gọi là cung thuận, các cung còn lại gọi là cung nghịch. Đồ thị Gf được gọi là đồ thị tăng luồng.

Ví dụ: Các số viết cạnh các cung của G ở hình 1 theo thứ tự là khả năng thông qua và luồng trên cung

Mạng G và luồng f. Đồ thị có trọng số Gf tương ứng.

Đường tăng luồng.Giả sử P = (s = v0,v1,v2,…,vk= t) là một đường đi từ s đến t trên đồ thị tăng luồng Gf. Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi P. Xây dựng luồng f' trên mạng G theo quy tắc sau:

  f(u,v) + d, nếu (u,v) ∈ P là cung thuận  f(u,v) =  f(u,v) - d, nếu (u,v) ∈ P là cung nghịch  f(u,v), nếu (u,v) không ∈ P 

Đường tăng luồng

Dễ dàng kiểm tra được rằng f' được xây dựng như trên là luồng trong mạng và val(f')= val(f) + d. Ta sẽ gọi thủ tục biến đổi luồng vừa nêu là tăng luồng dọc theo đường P.

Luồng trên mạng G trước và sau khi tăng.

Sau biến đổi ta có luồng mới mang giá trị 9. val(f,) = 4 + 3 - 3 + 2 + 3 = 9

Thuật toán Ford-Fulkerson

Đến Thuật toán

Luồng cực đại với khả năng thông qua các cung và các đỉnh:

Giả sử trong đồ thị G = (V,E), ngoài khả năng thông qua của các cung c(u,v), ở mỗi đỉnh còn có khả năng thông qua của đỉnh là d(v), và đòi hỏi tổng luồng đi vào đỉnh v không còn vượt quá d(v), tức là ∑ f (w, v) < d(v), với w ∈ V

Cần phải tìm luồng cực đại giữa s và t trong mạng như vậy.Xây dựng một mạng G’ sao cho: mỗi đỉnh v của G tương ứng với hai đỉnh (v+ v-) trong G’, mỗi cung (u,v) trong G ứng với cung (u,v+) trong G’ mỗi cung (v,w) trong G ứng với cung (v- w+) trong G’. Ngoài ra, mỗi cung (v+ v-) trong G’ có khả năng thông qua là d(v), tức là bằng khả năng thông qua của đỉnh v trong G.

Giải quyết bài toánTừ mạng G = (V,E) khả năng thông qua các cung và các đỉnh. Ta sẽ giải quyết theo hai bước sau:

* Xác định mạng G’. * Tìm luồng cực đại trong mạng G’. Bắt đầu từ luồng 0 với khả năng thông qua cung. 

Ma trận biểu diễn đồ thị của bài toán luồng cực đại1 Biểu diễn mạng G với khả năng thông qua các cung và đỉnhGiả sử mạng G = (V,E), |V| = n. Ta có thể biểu diễn bởi ma trận trọng số A cấp n x n như sau:

A = ( a i j ) = { d i nếu  i = j c [ i , j ] nếu  [ i , j ] ∈ E 0 nếu  [ i , j ] ∉ E {\displaystyle A=(a_{ij})={\begin{cases}d_{i}&{\text{nếu }}i=j\\c[i,j]&{\text{nếu }}[i,j]\in E\\0&{\text{nếu }}[i,j]\not \in E\end{cases}}}

Trong đó: di là khả năng thông qua đỉnh i; C[i,j] khả năng thông qua cung [i,j].

2 Biểu diễn mạng G’ tương ứng với mạng G Mạng tương ứng với G = (V,E), |V | = n là mạng G’ = (V’,E’), |V’| = 2 |V |, |E’| = 2 |E | - 1. Được biểu diễn thông qua ma trận A’ cấp (2n x 2n) như sau:

A ′ = ( a i j ′ ) = { 0 nếu  i = j c [ i , j ] nếu  [ i , j ] ∈ E ′ {\displaystyle A^{\prime }=(a_{ij}^{\prime })={\begin{cases}0&{\text{nếu }}i=j\\c[i,j]&{\text{nếu }}[i,j]\in E^{\prime }\end{cases}}}

Như thí dụ trên có mạng G như sau:

ma tran g

Tương tự mạng G'

truoc

Áp dụng Thuật toán Ford-Fulkerson tìm luồng cực đại cho mạng G’ ta được mạng cực đại và ma trận biểu diễn nó như sau

sau ma

Giả mã luồng cực đại